#ifndef REGION_GROWING_H
#define REGION_GROWING_H

#include <CGAL/Linear_cell_complex.h>
#include <CGAL/Linear_cell_complex_constructors.h>
#include <CGAL/Linear_cell_complex_operations.h>
#include <CGAL/IO/Polyhedron_iostream.h>
#include <CGAL/IO/File_header_OFF.h>
#include <CGAL/IO/File_scanner_OFF.h>
#include <CGAL/Cartesian.h>
#include <algorithm>
#include "boost/random.hpp"

typedef int LccMarker;

template<typename LCC>
class RegionGrowing
{
private:

	typedef typename LCC::Dart_handle Dart_handle;

	struct GrowingNode
	{
		int region;
		Dart_handle child;
		Dart_handle parent;
	};

	LCC& m_lcc;
	LccMarker m_seedMarker;
	int m_nbRegion;
	boost::random::mt19937 m_rng;
	boost::random::uniform_int_distribution<> m_randomFacet;
	std::queue<GrowingNode> m_queue; //Stack to simulate recursive approach
	std::queue<GrowingNode> m_queueCriteria; //Stack to simulate recursive approach
	
public:
	RegionGrowing(LCC& lcc, int nbSeed) :
		m_lcc(lcc),
		m_randomFacet(0, lcc.template one_dart_per_cell<2>().size()-1),
		m_nbRegion(nbSeed)
	{
		m_rng.seed(static_cast<unsigned int>(std::time(0)));
		
		m_seedMarker = lcc.get_new_mark();
		
		const int nbRegion = nbSeed;
	}
	
	~RegionGrowing()
	{
		m_lcc.free_mark(m_seedMarker);
	}
	
	void markFacet(Dart_handle& dart, const LccMarker& marker)
	{
		for(
			typename LCC::template Dart_of_orbit_range<1>::const_iterator orbitIter = m_lcc.template darts_of_orbit<1>(dart).begin();
			orbitIter != m_lcc.template darts_of_orbit<1>(dart).end();
			++orbitIter)
		{
			m_lcc.mark(orbitIter, marker);
		}
	}
	
	void growingStep1()
	{
		//Unmark all facet
		for(
			typename LCC::template One_dart_per_cell_range<2>::iterator dartIter=m_lcc.template one_dart_per_cell<2>().begin();
			dartIter.cont();
			++dartIter)
		{
			m_lcc.template set_attribute<2>(dartIter, m_lcc.template create_attribute<2>());
			dartIter->template attribute<2>()->info() = -1;
		}
				
		//Generated random seed
		std::list<int> seedPosition;
		for(int i=0; i<m_nbRegion; i++)
		{
			int d;
			do
			{
				d = m_randomFacet(m_rng);
			}
			while(std::find(seedPosition.begin(), seedPosition.end(), d) != seedPosition.end());
			
			seedPosition.push_back(d);
		}
		seedPosition.sort();
		
		//Fill queue
		typename LCC::template One_dart_per_cell_range<2>::iterator dartIter=m_lcc.template one_dart_per_cell<2>().begin();
		int facetCursor = 0;
		int regionCursor = 0;
		for(std::list<int>::iterator iter = seedPosition.begin(); iter != seedPosition.end(); iter++)
		{
			while(facetCursor < *iter)
			{
				dartIter++;
				facetCursor++;
			}
			
			GrowingNode gn;
			gn.region = regionCursor;
			gn.child = dartIter;
			gn.parent = LCC::null_dart_handle;
			
			m_queue.push(gn);
			dartIter->template attribute<2>()->info() = regionCursor;
			//~ markFacet(dartIter, m_regionMarker[regionCursor]);
			markFacet(dartIter, m_seedMarker);
			regionCursor++;
		}
	}
	
	void growingStep2_core(bool criteria)
	{
		int facetCounter = 0;
		while(!m_queue.empty())
		{
			GrowingNode gn = m_queue.front();
			
			m_queue.pop();
			
			for(
				typename LCC::template Dart_of_orbit_range<1>::iterator orbitIter = m_lcc.template darts_of_orbit<1>(gn.child).begin();
				orbitIter.cont();
				++orbitIter)
			{
				Dart_handle neiDart = m_lcc.beta(orbitIter, 2);
				if(neiDart != LCC::null_dart_handle)
				{
					if(neiDart->template attribute<2>()->info() == -1)
					{
						typename LCC::Vector nChild = CGAL::compute_normal_of_cell_2<LCC>(m_lcc,neiDart);
						typename LCC::Vector nParent = CGAL::compute_normal_of_cell_2<LCC>(m_lcc,gn.child);
						
						nChild = nChild / CGAL::sqrt(nChild.squared_length());
						nParent = nParent / CGAL::sqrt(nParent.squared_length());
						
						double dotProduct = nChild * nParent;
						
						if(!criteria || dotProduct > 0.99)
						{
							GrowingNode newGn;
							newGn.region = gn.region;
							newGn.child = neiDart;
							newGn.parent = gn.child;
							
							m_queue.push(newGn);
							neiDart->template attribute<2>()->info() = gn.region;
							//~ markFacet(neiDart, m_regionMarker[gn.region]);
						}
						else if(criteria)
						{
							GrowingNode newGn;
							newGn.region = gn.region;
							newGn.child = neiDart;
							newGn.parent = gn.child;
							
							m_queueCriteria.push(newGn);
						}
					}
				}
			}
			
			facetCounter++;
			
			if(facetCounter % 100 == 0)
			{
				std::cout << "\r" << "Facet " << facetCounter << "           ";
				std::cout.flush();
			}
		}
		
		std::cout << std::endl;
	}
	
	void growingStep2()
	{
		growingStep2_core(true);
	}
	
	void growingStep3()
	{
		while(!m_queueCriteria.empty())
		{
			//~ markFacet(m_queueCriteria.front().child, m_regionMarker[m_queueCriteria.front().region]);
			m_queueCriteria.front().child->template attribute<2>()->info() = m_queueCriteria.front().region;
			
			m_queue.push(m_queueCriteria.front());
			m_queueCriteria.pop();
		}
		
		growingStep2_core(false);
	}
	
	LCC& lcc()
	{
		return m_lcc;
	}
	
	LccMarker seedMarker()
	{
		return m_seedMarker;
	}
	
	int nbRegion() const
	{
		return m_nbRegion;
	}
};

#endif
